/*****************************************************
Copyright (C) 2020. All rights reserved.
File name     ：Graph.c
Version       ：v1.0
Author        ：zhengqijun
Date          ：2020-04-15
Function List ：
Description   ：Adjacency Matrix
******************************************************/

#include "Graph.h"
#include <stdlib.h>   // for malloc
#include "FatalError.h"

#define MaxVertexNum     (16)

struct GraphNode {
    VertexType *Vertices;
    ArcType **Arcs;
    int NumVertex;
    int NumArc;
};

// Static Function Lists
static int LocateVertex(VertexType V, Graph G);

Graph Initialize(void) {
    Graph G;
    int i;

    /* Allocate graph */
    G = (Graph)malloc(sizeof(struct GraphNode));
    if (G == NULL) {
        FatalError("Out of space!!!");
    }

    /* Allocate the array for vertices */
    G->Vertices = (VertexType *)malloc(MaxVertexNum * sizeof(VertexType));
    if (G->Vertices == NULL) {
        FatalError("Out of space!!!");
    }

    /* Allocate the array for arcs */
    G->Arcs = (ArcType **)malloc(MaxVertexNum * sizeof(ArcType *));
    if (G->Arcs == NULL) {
        FatalError("Out of space!!!");
    }

    for (i = 0; i < MaxVertexNum; ++i) {
        G->Arcs[i] = (ArcType *)malloc(MaxVertexNum * sizeof(ArcType));
        if (G->Arcs[i] == NULL) {
            FatalError("Out of space!!!");
        }
    }

    MakeEmpty(G);

    return G;
}

void MakeEmpty(Graph G) {
    int i;
    int j;

    for (i = 0; i < MaxVertexNum; ++i) {
        for (j = 0; j < MaxVertexNum; ++j) {
            G->Arcs[i][j] = Infinity;
        }
    }

    G->NumVertex = 0;
    G->NumArc = 0;
}

void Destroy(Graph G) {
    int i;

    for (i = 0; i < MaxVertexNum; ++i) {
        free(G->Arcs[i]);
    }

    free(G->Arcs);
    free(G->Vertices);
    free(G);
}

int IsEmpty(Graph G) {
    return G->NumVertex == 0;
}

int IsFull(Graph G) {
    return G->NumVertex == MaxVertexNum;
}

/* If Vertex is found, then index of returned */
/* the location */
static int LocateVertex(VertexType V, Graph G) {
    int i;

    for (i = 0; i < G->NumVertex; ++i) {
        /* Probably need strcmp! */
        if (V == G->Vertices[i]) {
            return i;
        }
    }

    return -1;
}

void InsertVertex(VertexType V, Graph G) {
    if (!IsFull(G)) {
        // Check vertex in graph
        if (LocateVertex(V, G) != -1) {
            Error("Vertex V already exists!");
        } else {
            G->Vertices[G->NumVertex] = V;
            G->Arcs[G->NumVertex][G->NumVertex] = 0;
            ++G->NumVertex;
        }
    }
}

void InsertArc(VertexType VS, VertexType VE, ArcType Weight, Graph G) {
    int StartIndex;
    int EndIndex;

    StartIndex = LocateVertex(VS, G);
    EndIndex = LocateVertex(VE, G);

    // Check vertex in graph
    if (StartIndex == -1) {
        Error("Vertex VS is not found!");
    } else if (EndIndex == -1) {
        Error("Vertex VE is not found!");
    } else {
        if (StartIndex != EndIndex) {
            G->Arcs[StartIndex][EndIndex] = Weight;
            ++G->NumArc;
#ifdef UndirectedGraph
            G->Arcs[EndIndex][StartIndex] = Weight;
            ++G->NumArc;
#endif
        } else {
            Error("Vertex VS is same as Vertex VE!");
        }
    }
}

void RemoveVertex(VertexType V, Graph G) {
    int Index;
    int i;

    if (!IsEmpty(G)) {
        Index = LocateVertex(V, G);

        // Check vertex in graph
        if (Index != -1) {
            if (Index != G->NumVertex) {
                // Delete vertex
                G->Vertices[Index] = G->Vertices[G->NumVertex - 1];

                // Delete arcs associated with vertex
                for (i = 0; i < G->NumVertex; ++i) {
                    if (G->Arcs[Index][i] != Infinity && G->Arcs[Index][i] != 0) {
                        --G->NumArc;
                    }

                    G->Arcs[Index][i] = G->Arcs[G->NumVertex - 1][i];
                }

                for (i = 0; i < G->NumVertex; ++i) {
                    if (G->Arcs[i][Index] != Infinity && G->Arcs[i][Index] != 0) {
                        --G->NumArc;
                    }

                    G->Arcs[i][Index] = G->Arcs[i][G->NumVertex - 1];
                }
            }

            // Update the number of vertices
            --G->NumVertex;
        }
    }
}

void RemoveArc(VertexType VS, VertexType VE, Graph G) {
    int StartIndex;
    int EndIndex;

    StartIndex = LocateVertex(VS, G);
    EndIndex = LocateVertex(VE, G);

    // Check vertex in graph
    if (StartIndex == -1) {
        Error("Vertex VS is not found!");
    } else if (EndIndex == -1) {
        Error("Vertex VE is not found!");
    } else {
        if (VS != VE) {
            G->Arcs[StartIndex][EndIndex] = Infinity;
            --G->NumArc;
#ifdef UndirectedGraph
            G->Arcs[EndIndex][StartIndex] = Infinity;
            --G->NumArc;
#endif
        } else {
            Error("Vertex VS is same as Vertex VE!");
        }
    }
}

int N(Graph G) {
    return G->NumVertex;
}

int E(Graph G) {
    return G->NumArc;
}

VertexType First(VertexType V, Graph G) {
    int i;
    int Index;

    Index = LocateVertex(V, G);
    if (Index == -1) {
        Error("Vertex V is not found!");
    } else {
        for (i = 0; i < G->NumVertex; ++i) {
            if (G->Arcs[Index][i] != Infinity) {
                break;
            }
        }
    }

    return G->Vertices[i];
}

VertexType Next(VertexType VS, VertexType VE, Graph G) {
    int i;
    int StartIndex;
    int EndIndex;

    StartIndex = LocateVertex(VS, G);
    EndIndex = LocateVertex(VE, G);

    if (StartIndex == -1) {
        Error("Vertex VS is not found!");
    } else if (EndIndex == -1) {
        Error("Vertex VE is not found!");
    } else {
        for (i = EndIndex + 1; i < G->NumVertex; ++i) {
            if (G->Arcs[StartIndex][i] != Infinity &&
                G->Arcs[StartIndex][i] != 0) {
                break;
            }
        }
    }

    return G->Vertices[i];
}

ArcType Weight(VertexType VS, VertexType VE, Graph G) {
    int StartIndex;
    int EndIndex;

    StartIndex = LocateVertex(VS, G);
    EndIndex = LocateVertex(VE, G);

    if (StartIndex != -1 && EndIndex != -1) {
        return G->Arcs[StartIndex][EndIndex];
    } else {
        return Infinity;
    }
}

VertexType Vertex(int Index, Graph G) {
    return G->Vertices[Index];
}

// EOF

